191C - Fools and Roads - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define ld long double
#define el '\n'
#define PI 3.14159265358979323846
#define ordered_set tree<pair<pair<int,int>,int>, null_type,less<pair<pair<int,int>, int>>, rb_tree_tag,tree_order_statistics_node_update>
int dx[] = {1,-1,0,0,-1,-1,1,1};
int dy[] = {0,0,1,-1,-1,1,1,-1};
const int N = 1e5 + 10, M = 1e4, mod = 1e9 + 7, LOG = 20, inf = 1e9 + 10;

int up[N][LOG], sum[N], depth[N], sol[N];
vector<pair<int,int>> g[N];

void dfsSet(int node, int par) {
    up[node][0] = par;
    depth[node] = depth[par] + 1;

    for (int i = 1; i < LOG; i++)
        up[node][i] = up[up[node][i - 1]][i - 1];

    for (auto child : g[node]) {
        if (child.first == par)
           continue;

        dfsSet(child.first, node);
    }
}

int dfs(int node, int par) {
    int ret = sum[node];

    for (auto child : g[node])
    {
        if (child.first == par)
            continue;

        sol[child.second] = dfs(child.first, node);
        ret += sol[child.second];
    }

    return ret;
}

int LCA(int u, int v) {
    if (depth[u] < depth[v])
        swap(u, v);

    int k = depth[u] - depth[v];
    for (int i = LOG - 1; i >= 0; i--) {
        if ((1 << i) & k)
            u = up[u][i];
    }

    if (u == v)
        return u;

    for (int i = LOG - 1; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }

    return up[u][0];
}

int getDist(int u, int v) {
    int lca = LCA(u, v);
    return depth[u] + depth[v] - 2 * depth[lca];
}

void doWork() {
    int n;
    cin >> n;

    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;

        g[u].emplace_back(v,i + 1);
        g[v].emplace_back(u,i + 1);
    }

    dfsSet(1,0);

    int q;
    cin >> q;
    while (q--)
    {
        int u, v;
        cin >> u >> v;

        sum[u]++, sum[v]++, sum[LCA(u,v)] -= 2;
    }

    dfs(1,0);

    for (int i = 1; i < n; i++)
        cout << sol[i] << ' ';
}

int main() {

    fast
    int T = 1;
    //cin >> T;
    while (T--)
        doWork();


    return 0;
}